"""
计数排序：
    - 对列表进行排序, 已知列表中的数范围都在0到100之间。设计时间复杂度为O(n)的算法

"""
from SortingAlgorithm.cal_time.cal_time import cal_time


@cal_time(name="计数排序时间")
def count_sort(li, max_count=100):
    count = [0 for _ in range(max_count+1)]
    for val in li:
        count[val] += 1
    li.clear()
    for ind, val in enumerate(count):
        for i in range(val):
            li.append(ind)


@cal_time(name="标准模块排序时间")
def sys_sort(li):
    li.sort()


if __name__ == "__main__":
    import random, copy
    li = [random.randint(0, 100) for _ in range(1000000)]

    li1 = copy.deepcopy(li)
    li2 = copy.deepcopy(li)

    count_sort(li1)
    sys_sort(li2)
